#include<stdio.h>
#include<stdlib.h>

typedef struct T_Node{
	int d;
	struct T_Node *next;
} Node, *List;

void LinkReverse(List *pla);

void createlink(List *pla)
{
	int i;
	Node *p;

	*pla = (Node *)malloc(sizeof(Node));     //创建头结点
	p = *pla;

	for(i = 1; i <=10;i++)
	{
		p->next = (Node *)malloc(sizeof(Node));		
		p = p->next;
		p->d = i;
		p->next = NULL;
	}
}


void main()
{
	List la, p;
	int i;

	createlink(&la);
	LinkReverse(&la);

	p = la->next;
	for(i = 1; i <=10;i++)
	{
		printf("%4d",p->d);
		p = p->next;
	}
	printf("\n");
}


//传入参数 表头节点地址的地址(指向表头节点(Node)的指针 的地址)
//题目所求函数 功能:翻转链表
void LinkReverse(List *pla){
	Node *p1,*p2,*p3;
	List la = *pla;//将间接访问的参数转化成方便的形式

	//单独处理:由于只有零一二个节点特殊情况特殊处理
	//当然可以用更优雅间接的"!la->next",但是这样表达不如这种直观
	if(la->next==NULL){
		return;
	}
	if(la->next->next==NULL){
		return;
	}
	if(la->next->next->next==NULL){
		p1=la->next;
		p2=la->next->next;
		la->next=p2;
		p2->next=p1;
		p1->next=NULL;
	}


	//普遍的情况:
	//需要先思考好为什么要三个节点处理再往后看代码(建议打草稿思考)
	p1=la->next;//第一个节点
	p2=p1->next;//第二个节点
	p3=p2->next;//第三个节点(根本作用是记录p2->next)
	p1->next=NULL;//将原第一个节点变为新的最后一个节点
	//使每一个后一个节点指向前一个节点
	do{
		p2->next=p1;//使后一个节点指向前一个节点

		p1=p2;
		p2=p3;
		p3=p3->next;

	}while(p3!=NULL);
	//将原最后一个节点指向原倒数第二个节点
	p2->next=p1;
	//将原最后一个节点作为首节点
	la->next=p2;


};
/*
设计一个函数
void LinkReverse(List *pla)
其功能将带头结点的单向链表反转。la是一个带头结点的链表，函数的目的是逆转这个链表，也就是第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，以此类推。
该函数的空间复杂度为O(1），
也就是该函数不能定义数组变量和使用动态分配函数。
其中List是如下结构体：
typedef struct T_Node{
	int d;
	struct T_Node *next;
} Node, *List;
如下的main函数执行后
//创建头指针为la的链表
void createlink(List *pla)
{
	int i;
	Node *p;

	*pla = (Node *)malloc(sizeof(Node));     //创建头结点
	p = *pla;

	for(i = 1; i <=10;i++)
	{
		p->next = (Node *)malloc(sizeof(Node));		
		p = p->next;
		p->d = i;
		p->next = NULL;
	}
}


void main( )
{
	List la, p;
	int i;

	createlink(&la);
	LinkReverse(&la);

	p = la->next;
	for(i = 1; i <=10;i++)
	{
		printf("%4d",p->d);
		p = p->next;
	}
	printf("\n");
}
执行的结果为
  10   9   8   7   6   5   4   3   2   1
*/